package com.leetcode.array.removeElement.demo1;

/**
 * @Author Zan
 * @Create 2024/5/8 10:30
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/remove-element/description/   移除元素
 */
public class Test {
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,2,3};
        // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
        Solution4 solution = new Solution4();
        int len = solution.removeElement(nums, 2);

        // 在函数里修改输入数组对于调用者是可见的。
        // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
        for (int i = 0; i < len; i++) {
            System.out.print(nums[i]);
        }
    }
}

// 暴力求解法
class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                // 后面的前移
                for (int j = i + 1; j < nums.length; j++) {
                    nums[j - 1] = nums[j];
                }
                size--;
                i--;
            }
        }
        return size;
    }
}

// 双指针 - 快慢指针
class Solution2 {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        int fastIndex = 0;
        int slowIndex = 0;
        for (int i = 0; i < size; i++) {
            nums[slowIndex] = nums[fastIndex];
            if (nums[i] != val) {
                fastIndex++;
                slowIndex++;
            } else { // 相等的时候
                fastIndex++;
                size--;
                i--;
            }
        }
        return size;
    }
}

// 快慢指针（第二版）
class Solution3 {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

// 相向双指针法（版本二）
class Solution4 {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right]; // 将最后面的移到最前面
                right--;
            }else {
                // 这里兼容了right指针指向的值与val相等的情况
                left++;
            }
        }
        return left;
    }
}
